REWRITINGS OF QUERIES Q1,Q2 AND Q3 FOR VARIOUS LENGTHS.
ALL OTHER REWRITINGS CAN BE EXTRACTED AS A SUBSET OF THE LONGEST ONE SPECIFIED IN THIS DOCUMENT.

REWRITINGS OF THE QUERY Q1 FOR LENGTHS 2,3,4:

SELECT ?act WHERE{{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act}

UNION {{ ?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act2  . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act}}}

SELECT ?act WHERE{{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act}

UNION { ?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act2  . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act}

UNION {?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act3  . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act1  }}

SELECT ?act WHERE{{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act}

UNION { ?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act2  . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act}

UNION {?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act3  . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act  }

UNION {?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act4  . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act  }}

REWRITING OF THE QUERY Q2 FOR LENGTH 5:

SELECT DISTINCT ?act ?dir {
	{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir}
	UNION {
	?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir
	}
	UNION {
	?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov3 <http://data.linkedmdb.org/resource/movie/director> ?dir
	}
	UNION {
	?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov3 <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov4 <http://data.linkedmdb.org/resource/movie/director> ?dir
	}
	UNION {
	?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act5 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act5 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov5 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov5 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov3 <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov4 <http://data.linkedmdb.org/resource/movie/director> ?dir . ?mov5 <http://data.linkedmdb.org/resource/movie/director> ?dir
	}
}

REWRITING OF THE QUERY Q3 FOR LENGTH 4:

KB act-dir

SELECT DISTINCT ?act WHERE{
				 {?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?dir <http://data.linkedmdb.org/resource/movie/director_name> ?x . ?y <http://data.linkedmdb.org/resource/movie/actor_name> ?x}
				 UNION{
					{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?dir <http://data.linkedmdb.org/resource/movie/director_name> ?x . ?y <http://data.linkedmdb.org/resource/movie/actor_name> ?x . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir2 . ?dir2 <http://data.linkedmdb.org/resource/movie/director_name> ?x2 . ?y2 <http://data.linkedmdb.org/resource/movie/actor_name> ?x2}
				}
				 UNION{
					{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?dir <http://data.linkedmdb.org/resource/movie/director_name> ?x . ?y <http://data.linkedmdb.org/resource/movie/actor_name> ?x . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir2 . ?dir2 <http://data.linkedmdb.org/resource/movie/director_name> ?x2 . ?y2 <http://data.linkedmdb.org/resource/movie/actor_name> ?x2 . ?mov3 <http://data.linkedmdb.org/resource/movie/director> ?dir3 . ?dir3 <http://data.linkedmdb.org/resource/movie/director_name> ?x3 . ?y3 <http://data.linkedmdb.org/resource/movie/actor_name> ?x3}
				}
				 UNION{
					{?mov <http://data.linkedmdb.org/resource/movie/actor> <http://data.linkedmdb.org/resource/actor/29539> . ?mov <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act4 . ?mov2 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act3 . ?mov3 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act2 . ?mov4 <http://data.linkedmdb.org/resource/movie/actor> ?act . ?mov <http://data.linkedmdb.org/resource/movie/director> ?dir . ?dir <http://data.linkedmdb.org/resource/movie/director_name> ?x . ?y <http://data.linkedmdb.org/resource/movie/actor_name> ?x . ?mov2 <http://data.linkedmdb.org/resource/movie/director> ?dir2 . ?dir2 <http://data.linkedmdb.org/resource/movie/director_name> ?x2 . ?y2 <http://data.linkedmdb.org/resource/movie/actor_name> ?x2 . ?mov3 <http://data.linkedmdb.org/resource/movie/director> ?dir3 . ?dir3 <http://data.linkedmdb.org/resource/movie/director_name> ?x3 . ?y3 <http://data.linkedmdb.org/resource/movie/actor_name> ?x3 . ?mov4 <http://data.linkedmdb.org/resource/movie/director> ?dir4 . ?dir4 <http://data.linkedmdb.org/resource/movie/director_name> ?x4 . ?y4 <http://data.linkedmdb.org/resource/movie/actor_name> ?x4}
				}
				}